package 递归;

/**
 * [类名称][功能描述]
 *
 * @author
 * @version [版本], 创建时间:   更新时间:
 */
public class 迷宫问题 {
    public static void main(String[] args) {
//        使用二维数组创建迷宫
//        规定map数组的值  0 表示可以走   1 表示障碍物
        int[][] map = new int[8][7];
//        将最上边和最下边的设置成障碍物
        for (int i =0;i < 7 ;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }
//        将左右两边设置成障碍物
        for (int i =0;i<8;i++){
            map[i][0]=1;
            map[i][6]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
//      循环二维数组  输出当前地图
        System.out.println("---当前地图---");
        for (int i =0;i<map.length;i++){
            for (int j=0;j<map[i].length;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        T t = new T();
//        老鼠的初始位置
        t.find(map,1,1);
        System.out.println("-------路径-------");
        for (int i =0;i<map.length;i++){
            for (int j=0;j<map[i].length;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }


    }
    public static class T{
       /* find 方法用来找出迷宫的路径
       * 如果找到返回true  否则返回false
       * map 表示迷宫  i j 为老鼠坐标
       * 递归的找路   0 表示可以走   1 表示障碍物  2 表示可以走  3  表示走过但是不通
       * 当map[6][5]=2  说明找到终点了
       * 找路的策略   下-右-上-左
       */
        public boolean find(int[][] map,int i,int j){
            if (map[6][5]==2){
                return true;
            }else {
                if (map[i][j]==0){
//                    假设路可以走通
                    map[i][j]=2;
//                    使用策略，确定是否可以走通
//                    下-右-上-左
                    if (find(map, i+1, j)){ // 下
                        return true;
                    } else if (find(map, i, j+1)) { // 右
                        return true;
                    } else if (find(map, i-1, j)) { // 上
                        return true;
                    } else if (find(map, i, j-1)) { // 左
                        return true;
                    }else {
                        map[i][j]=3;
                        return false;
                    }
                }else {
                    return false;
                }
            }
        }
    }
}
